package com.xxd.algo.newcode.mid02.class04;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-10-16 13:22
 */
public class Code03_PalindromeMinAdd {

    public static int f(String str, int L, int R) {
        if (L < 0 || R >= str.length() || L >= R) {
            return 0;
        }

        int ans = Integer.MAX_VALUE;

        if (str.charAt(L) == str.charAt(R)) {// 头 和 尾 是一样的
            ans = Math.min(f(str, L + 1, R - 1), ans);
        }

        ans = Math.min(Math.min(ans, f(str, L, R - 1) + 1), f(str, L + 1, R) + 1);
        return ans;
    }

    public static int process(String str) {
        return f(str, 0, str.length() - 1);
    }
}
